{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bold Words in String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: boldWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串中的加粗单词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个关键词集合&nbsp;<code>words</code> 和一个字符串&nbsp;<code>s</code>，将所有 <code>s</code> 中出现的关键词&nbsp;<code>words[i]</code>&nbsp;加粗。所有在标签&nbsp;<code>&lt;b&gt;</code>&nbsp;和&nbsp;<code>&lt;b&gt;</code>&nbsp;中的字母都会加粗。</p>\n",
    "\n",
    "<p>加粗后返回 <code>s</code> 。返回的字符串需要使用尽可能少的标签，当然标签应形成有效的组合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = [\"ab\",\"bc\"], s = \"aabcd\"\n",
    "<strong>输出:</strong> \"a&lt;b&gt;abc&lt;/b&gt;d\"\n",
    "<strong>解释: </strong>注意返回 <code>\"a&lt;b&gt;a&lt;b&gt;b&lt;/b&gt;c&lt;/b&gt;d\"</code> 会使用更多的标签，因此是错误的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> words = [\"ab\",\"cb\"], s = \"aabcd\"\n",
    "<strong>输出:</strong> \"a&lt;b&gt;ab&lt;/b&gt;cd\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;= words.length &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 10</code></li>\n",
    "\t<li><code>s</code>&nbsp;和&nbsp;<code>words[i]</code>&nbsp;由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注：</strong>此题与「616 - 给字符串添加加粗标签」相同 - <a href=\"https://leetcode-cn.com/problems/add-bold-tag-in-string/\">https://leetcode-cn.com/problems/add-bold-tag-in-string/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bold-words-in-string](https://leetcode.cn/problems/bold-words-in-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bold-words-in-string](https://leetcode.cn/problems/bold-words-in-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"ab\",\"bc\"]\\n\"aabcd\"', '[\"ab\",\"cb\"]\\n\"aabcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        site = []\n",
    "        for i in range(len(s)):\n",
    "            for word in words:\n",
    "                if s[i:i + len(word)] == word:\n",
    "                    a = i\n",
    "                    b = i + len(word)\n",
    "                    if site and site[-1][-1] >= a:\n",
    "                        site[-1][-1] = max(b, site[-1][-1])\n",
    "                    else:\n",
    "                        site.append([a, b])\n",
    "        ans = ''\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        now = 0\n",
    "        while i < n:\n",
    "            if now < len(site) and i == site[now][0]:\n",
    "                ans += '<b>' + s[i:site[now][1]] + '</b>'\n",
    "                i = site[now][1]\n",
    "                now += 1\n",
    "            else:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        n = len(s)\n",
    "        mask = [False]*n\n",
    "        for i in range(n):\n",
    "            for x in words:\n",
    "                if i + len(x) <= n and s[i:i + len(x)] == x:\n",
    "                    for j in range(i,i + len(x)):\n",
    "                        mask[j] = True\n",
    "        ans = ''\n",
    "        for i,x in enumerate(mask):\n",
    "            if x and (i == 0 or not mask[i - 1]):\n",
    "                ans += '<b>'\n",
    "            ans += s[i]\n",
    "            if x and (i == n - 1 or not mask[i + 1]):\n",
    "                ans += '</b>'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        n = len(s)\n",
    "        nums = []\n",
    "        words = set(words)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if s[i: j + 1] in words:\n",
    "                    nums.append([i, j])\n",
    "        if not nums: return s\n",
    "        res = [nums[0]]\n",
    "        m = len(nums)\n",
    "        for i in range(1, m):\n",
    "            if nums[i][0] <= res[-1][1] + 1:\n",
    "                res[-1][1] = max(res[-1][1], nums[i][1])\n",
    "            else:\n",
    "                res.append(nums[i])\n",
    "        m = len(res)\n",
    "        ans = ''\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < n:\n",
    "            if j >= m or i < res[j][0]:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += '<b>'\n",
    "                while i <= res[j][1]:\n",
    "                    ans += s[i]\n",
    "                    i += 1\n",
    "                ans += '</b>'\n",
    "                j += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        result, p, prev = '', [0] * (len(s)+1), 0\n",
    "        for w in words:\n",
    "            i, n = s.find(w), len(w)\n",
    "            while i >= 0:\n",
    "                p[i] += 1\n",
    "                p[i+n] -= 1\n",
    "                i = s.find(w, i+1)\n",
    "        for c, x in zip_longest(s, accumulate(p), fillvalue=''):\n",
    "            if x and not prev:\n",
    "                result += '<b>'\n",
    "            elif not x and prev:\n",
    "                result += '</b>'\n",
    "            result += c\n",
    "            prev = x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        n = len(s)\n",
    "        nums = []\n",
    "        words = set(words)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if s[i: j + 1] in words:\n",
    "                    nums.append([i, j])\n",
    "        if not nums: return s\n",
    "        res = [nums[0]]\n",
    "        m = len(nums)\n",
    "        for i in range(1, m):\n",
    "            if nums[i][0] <= res[-1][1] + 1:\n",
    "                res[-1][1] = max(res[-1][1], nums[i][1])\n",
    "            else:\n",
    "                res.append(nums[i])\n",
    "        m = len(res)\n",
    "        ans = ''\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < n:\n",
    "            if j >= m or i < res[j][0]:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += '<b>'\n",
    "                while i <= res[j][1]:\n",
    "                    ans += s[i]\n",
    "                    i += 1\n",
    "                ans += '</b>'\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        bold = [0] * len(s)\n",
    "\n",
    "        for word in words:\n",
    "            start = s.find(word)\n",
    "            \n",
    "            while start != -1:\n",
    "                for i in range(start, start + len(word)):\n",
    "                    bold[i] = 1\n",
    "                start = s.find(word, start + 1)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            if bold[i] and (i == 0 or not bold[i - 1]):\n",
    "                res.append(\"<b>\")\n",
    "            res.append(s[i])\n",
    "            if bold[i] and (i == len(s) - 1 or not bold[i + 1]):\n",
    "                res.append(\"</b>\")\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        n = len(s)\n",
    "        k = [False] * n\n",
    "        for word in words:\n",
    "            left = 0\n",
    "            while True:\n",
    "                idx = s.find(word, left)\n",
    "                if idx == -1:\n",
    "                    break\n",
    "                else:\n",
    "                    for i in range(len(word)):\n",
    "                        k[idx + i] = True\n",
    "                    left = idx + 1\n",
    "        res = \"\"\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while i < n and k[i] == False:\n",
    "                res += s[i]\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                break\n",
    "            res += \"<b>\"\n",
    "            while i < n and k[i] == True:\n",
    "                res += s[i]\n",
    "                i += 1\n",
    "            res += \"</b>\"\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words, S):\n",
    "        maxLen = 0\n",
    "        for word in words:\n",
    "            maxLen = max(maxLen, len(word))\n",
    "        \n",
    "        dict_set = set(words)\n",
    "        bolded = [0] * len(S)\n",
    "        \n",
    "        for i in range(len(S)):\n",
    "            for l in range(min(maxLen, len(S) - i), 0, -1):\n",
    "                if S[i:i+l] in dict_set:\n",
    "                    for j in range(i, i + l):\n",
    "                        bolded[j] = 1\n",
    "                    break\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(S)):\n",
    "            if bolded[i] and (i == 0 or not bolded[i-1]):\n",
    "                ans.append(\"<b>\")\n",
    "            ans.append(S[i])\n",
    "            if bolded[i] and (i == len(S) - 1 or not bolded[i+1]):\n",
    "                ans.append(\"</b>\")\n",
    "        \n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        n = len(s)\n",
    "        mask = [False] * n\n",
    "        end = 0  # 注意这个 end 必须放在 for 外面\n",
    "        # 完成遮掩动作，这样的话就可以覆盖题目中重合，连续了。\n",
    "        for i in range(n):\n",
    "            for word in words:\n",
    "                if s[i:].startswith(word):  # Java: s.startsWith(word, i)\n",
    "                    end = max(end, i + len(word))  # 左闭右开区间\n",
    "            if i < end:\n",
    "                mask[i] = True\n",
    "        ans = \"\"\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if mask[i]:\n",
    "                j = i\n",
    "                while j < n and mask[j]:  # j 最后会停在第一个不是 mask 的地方或 n\n",
    "                    j += 1\n",
    "                ans += \"<b>\" + s[i:j] + \"</b>\"\n",
    "                i = j\n",
    "            else:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        k=len(s)\n",
    "        keyword=[0]*k\n",
    "        for i in words:\n",
    "            n=len(i)\n",
    "            for j in range(k):\n",
    "                if s[j:j+n]==i:\n",
    "                    for x in range(j,j+n):\n",
    "                        keyword[x]=1\n",
    "        ans=\"\"\n",
    "        flag=0\n",
    "        for i in range(k):\n",
    "            if flag==0:\n",
    "                if keyword[i]==0:\n",
    "                    ans=ans+s[i]\n",
    "                else:\n",
    "                    ans=ans+\"<b>\"+s[i]\n",
    "                    flag=1\n",
    "            else:\n",
    "                if keyword[i]==0:\n",
    "                    ans=ans+\"</b>\"+s[i]\n",
    "                    flag=0\n",
    "                else:\n",
    "                    ans=ans+s[i]\n",
    "        if keyword[k-1]==1:\n",
    "            ans=ans+\"</b>\"\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "      intervals=[]\n",
    "      for word in words:\n",
    "        for l,r in self.get_pos(s,word):\n",
    "          intervals.append([l,r])\n",
    "      stack=[]\n",
    "      intervals.sort()\n",
    "      for l,r in intervals:\n",
    "        if stack and stack[-1][1]>=l:\n",
    "          stack[-1][1]=max(stack[-1][1],r)\n",
    "        else:\n",
    "          stack.append([l,r])\n",
    "      ans,end='',0\n",
    "      for l,r in stack:\n",
    "        ans+=s[end:l]\n",
    "        ans+='<b>'+s[l:r]+'</b>'\n",
    "        end=r\n",
    "      else:\n",
    "        ans+=s[end:]\n",
    "      return ans\n",
    "\n",
    "    def get_pos(self,word1,word2):\n",
    "      result=[]\n",
    "      for i in range(len(word1)):\n",
    "        if i+len(word2)>len(word1):\n",
    "          break\n",
    "        for j in range(len(word2)):\n",
    "          if word1[i+j]!=word2[j]:\n",
    "            break\n",
    "        else:\n",
    "          result.append([i,i+len(word2)])\n",
    "      return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        def findOccur(word:str)->List[List[int]]:\n",
    "            m,n=len(word),len(s)\n",
    "            intervals=[]\n",
    "            start=0\n",
    "            while start<n:\n",
    "                start=s.find(word,start)\n",
    "                # 没找到\n",
    "                if start==-1:\n",
    "                    break\n",
    "                # 找到了\n",
    "                else:\n",
    "                    # list[start,end]应该是一个闭区间，表示<br></br>的位置\n",
    "                    intervals.append([start, start + m])\n",
    "                    start+=1\n",
    "            return intervals\n",
    "        def mergeInterval(intervals: List[List[int]]) -> List[List[int]]:\n",
    "            if not intervals:\n",
    "                return []\n",
    "\n",
    "            intervals.sort()\n",
    "            ret = [intervals[0]]\n",
    "            for interval in intervals[1:]:\n",
    "                if interval[0] <= ret[-1][1]:\n",
    "                    ret[-1][1] = max(ret[-1][1], interval[1])\n",
    "                else:\n",
    "                    ret.append(interval)\n",
    "            return ret\n",
    "\n",
    "        def insertTag(intervals:List[List[int]])->str:\n",
    "            n=len(intervals)\n",
    "            ret:str=\"\"\n",
    "            i,j=0,0\n",
    "            while i<len(s) and j<len(intervals):\n",
    "                # 还没碰到下一个需要添加<br></br>的区间\n",
    "                start=intervals[j][0]\n",
    "                end=intervals[j][1]\n",
    "                ret=ret+s[i:start]\n",
    "                # 添加<br>[start,end)</br>\n",
    "                ret=ret+\"<b>\"+s[start:end]+\"</b>\"\n",
    "                i=end\n",
    "                j+=1\n",
    "            ret=ret+s[i:]\n",
    "            return ret\n",
    "                \n",
    "\n",
    "        intervals=[]\n",
    "        for word in words:\n",
    "            intervals.extend(findOccur(word))\n",
    "        intervals=mergeInterval(intervals)\n",
    "        return insertTag(intervals)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        mark = []\n",
    "        for word in words:\n",
    "            start = 0\n",
    "            while word in s[start:]:\n",
    "                start = s.find(word, start) + 1\n",
    "                mark.append([start - 1, start - 1 + len(word)])\n",
    "        mark = collections.deque(self.merge(mark))\n",
    "        b = []\n",
    "        fb = []\n",
    "        for m in mark:\n",
    "            b.append(m[0])\n",
    "            fb.append(m[1])\n",
    "        ans = ''\n",
    "        for i, c in enumerate(s):\n",
    "            if b:\n",
    "                if i == b[0]:\n",
    "                    ans += '<b>'\n",
    "                    b = b[1:]\n",
    "            if fb:\n",
    "                if i == fb[0]:\n",
    "                    ans += '</b>'\n",
    "                    fb = fb[1:]\n",
    "            ans += c\n",
    "        if fb:\n",
    "            ans += '</b>'\n",
    "        return ans\n",
    "    \n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        merged = []\n",
    "        for interval in intervals:\n",
    "            if not merged or merged[-1][1] < interval[0]:\n",
    "                merged.append(interval)\n",
    "            else:\n",
    "                merged[-1][1] = max(merged[-1][1], interval[1])\n",
    "        return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        mark = []\n",
    "        for word in words:\n",
    "            start = 0\n",
    "            while word in s[start:]:\n",
    "                start = s.find(word, start) + 1\n",
    "                mark.append([start - 1, start - 1 + len(word)])\n",
    "        mark = collections.deque(self.merge(mark))\n",
    "        b = []\n",
    "        fb = []\n",
    "        for m in mark:\n",
    "            b.append(m[0])\n",
    "            fb.append(m[1])\n",
    "        ans = ''\n",
    "        for i, c in enumerate(s):\n",
    "            if b:\n",
    "                if i == b[0]:\n",
    "                    ans += '<b>'\n",
    "                    b = b[1:]\n",
    "            if fb:\n",
    "                if i == fb[0]:\n",
    "                    ans += '</b>'\n",
    "                    fb = fb[1:]\n",
    "            ans += c\n",
    "        if fb:\n",
    "            ans += '</b>'\n",
    "        return ans\n",
    "    \n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        merged = []\n",
    "        for interval in intervals:\n",
    "            if not merged or merged[-1][1] < interval[0]:\n",
    "                merged.append(interval)\n",
    "            else:\n",
    "                merged[-1][1] = max(merged[-1][1], interval[1])\n",
    "        return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        def findOccur(word:str)->List[List[int]]:\n",
    "            m,n=len(word),len(s)\n",
    "            intervals=[]\n",
    "            start=0\n",
    "            while start<n:\n",
    "                start=s.find(word,start)\n",
    "                # 没找到\n",
    "                if start==-1:\n",
    "                    break\n",
    "                # 找到了\n",
    "                else:\n",
    "                    # tuple(start,end)应该是一个闭区间，表示<br></br>的位置\n",
    "                    intervals.append([start, start + m])\n",
    "                    start+=1\n",
    "            return intervals\n",
    "        def mergeInterval(intervals: List[List[int]]) -> List[List[int]]:\n",
    "            if not intervals:\n",
    "                return []\n",
    "\n",
    "            intervals.sort()\n",
    "            ret = [intervals[0]]\n",
    "            for interval in intervals[1:]:\n",
    "                if interval[0] <= ret[-1][1]:\n",
    "                    ret[-1][1] = max(ret[-1][1], interval[1])\n",
    "                else:\n",
    "                    ret.append(interval)\n",
    "            return ret\n",
    "\n",
    "        def insertTag(intervals:List[List[int]])->str:\n",
    "            n=len(intervals)\n",
    "            ret:str=\"\"\n",
    "            i,j=0,0\n",
    "            while i<len(s) and j<len(intervals):\n",
    "                # 还没碰到下一个需要添加<br></br>的区间\n",
    "                start=intervals[j][0]\n",
    "                end=intervals[j][1]\n",
    "                ret=ret+s[i:start]\n",
    "                # 添加<br>[start,end)</br>\n",
    "                ret=ret+\"<b>\"+s[start:end]+\"</b>\"\n",
    "                i=end\n",
    "                j+=1\n",
    "            ret=ret+s[i:]\n",
    "            return ret\n",
    "                \n",
    "\n",
    "        intervals=[]\n",
    "        for word in words:\n",
    "            intervals.extend(findOccur(word))\n",
    "        intervals=mergeInterval(intervals)\n",
    "        return insertTag(intervals)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Interval:\n",
    "    def __init__(self):\n",
    "        self.sl = SortedList([(-inf, -inf), (inf, inf)])\n",
    "\n",
    "    def add(self, start, end) -> None:\n",
    "        x, y = start, end\n",
    "        p = self.sl.bisect_left((start, end))\n",
    "        while self.sl[p][0] <= end:\n",
    "            x, y = min(x, self.sl[p][0]), max(y, self.sl[p][1])\n",
    "            self.sl.pop(p)\n",
    "            p = self.sl.bisect_left((start, end))\n",
    "        while start <= self.sl[p-1][1]:\n",
    "            x, y = min(x, self.sl[p-1][0]), max(y, self.sl[p-1][1])\n",
    "            self.sl.pop(p-1)\n",
    "            p = self.sl.bisect_left((start, end))\n",
    "        self.sl.add((x, y))\n",
    "\n",
    "    def is_intersect(self, start, end) -> bool:\n",
    "        p = self.sl.bisect_left((start, end))\n",
    "        return self.sl[p][0] < end or start < self.sl[p-1][1]\n",
    "\n",
    "    def get_intersections(self, start, end) -> list:\n",
    "        p = self.sl.bisect_left((start, end))\n",
    "        l, r = p-1, p\n",
    "        rnt = []\n",
    "        while r < len(self.sl) and self.sl[r][0] < end:\n",
    "            rnt.append((max(start, self.sl[r][0]), min(end, self.sl[r][1])))\n",
    "            r += 1\n",
    "        while l >= 0 and start < self.sl[l][1]:\n",
    "            rnt.append((max(start, self.sl[l][0]), min(end, self.sl[l][1])))\n",
    "            l -= 1\n",
    "        return rnt\n",
    "\n",
    "    def get_intervals(self) -> list:\n",
    "        return list(self.sl)[1:-1]\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        n = len(s)\n",
    "        inter = Interval()\n",
    "        for word in words:\n",
    "            for i in range(n):\n",
    "                if s[i:i+len(word)] == word:\n",
    "                    inter.add(i, i+len(word))\n",
    "        s = list(s)\n",
    "        for l, r in inter.get_intervals()[::-1]:\n",
    "            s.insert(r, r\"</b>\")\n",
    "            s.insert(l, r\"<b>\")\n",
    "        return \"\".join(s)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def boldWords(self, words: List[str], s: str) -> str:\n",
    "        mark = []\n",
    "        for word in words:\n",
    "            start = 0\n",
    "            while word in s[start:]:\n",
    "                start = s.find(word, start) + 1\n",
    "                mark.append([start - 1, start - 1 + len(word)])\n",
    "        mark = collections.deque(self.merge(mark))\n",
    "        b = []\n",
    "        fb = []\n",
    "        for m in mark:\n",
    "            b.append(m[0])\n",
    "            fb.append(m[1])\n",
    "        ans = ''\n",
    "        for i, c in enumerate(s):\n",
    "            if b:\n",
    "                if i == b[0]:\n",
    "                    ans += '<b>'\n",
    "                    b = b[1:]\n",
    "            if fb:\n",
    "                if i == fb[0]:\n",
    "                    ans += '</b>'\n",
    "                    fb = fb[1:]\n",
    "            ans += c\n",
    "        if fb:\n",
    "            ans += '</b>'\n",
    "        return ans\n",
    "    \n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        merged = []\n",
    "        for interval in intervals:\n",
    "            if not merged or merged[-1][1] < interval[0]:\n",
    "                merged.append(interval)\n",
    "            else:\n",
    "                merged[-1][1] = max(merged[-1][1], interval[1])\n",
    "        return merged"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
